//
// Created by 高森森 on 2022/2/11.
//

#ifndef LEETCODE_SOLUTIOON37_H
#define LEETCODE_SOLUTIOON37_H
#include<iostream>
#include<vector>
#include<bitset>
#include <memory.h>

using namespace std;

class Solutioon37 {
public:

    int minTrioDegree(int n, vector<vector<int>>& edges) {
        const int INF=0X3f3f3f3f;
        vector<int>indegree(n+1,0);
        int res=INF;
        vector<vector<int>>graph(n+1,vector<int>(n+1,0));
        for(auto &edge:edges){
            indegree[edge[0]]++;
            indegree[edge[1]]++;
            graph[edge[0]][edge[1]]=1;
            graph[edge[1]][edge[0]]=1;
        }
        for(int i=1;i<=n;i++){
            //最小为1，可以不需要再寻找其他了
            if(res==0)
            {
                break;
            }
            for(int j=1;j<=n;j++){
                if(graph[i][j]==1) {
                for(int k=1;k<=n;k++)
                    if(graph[i][k]==1&&graph[j][k]==1){
                        res=min(res,indegree[i]+indegree[j]+indegree[k]-6);
                    }
                }
            }
        }
        return res==INF?-1:res;
    }
    int minTrioDegree2(int n, vector<vector<int>>& edges) {
        const int INF=0x3f3f3f3f;
        int res=INF;
        bitset<401>graph[n+1];
        int degree[n+1];
        memset(degree,0, sizeof(degree));
        for(int i=1;i<=n;i++)
        {
            bitset<401>temp{0};
            graph[i]=temp;
        }
        for(auto e:edges){
            graph[e[0]].set(e[1]);
            graph[e[1]].set(e[0]);
            degree[e[0]]++;
            degree[e[1]]++;
        }
        for(auto e:edges){
            bitset<401>neigh=graph[e[0]]&graph[e[1]];
            for(int i=1;i<=n;i++){
                if(neigh[i]){
                    res=min(res,degree[e[0]]+degree[e[1]]+degree[i]-6);
                }
            }
        }
        return res==INF?-1:res;
    }
};


#endif //LEETCODE_SOLUTIOON37_H
